package org.atovio.structure.tree;

import org.atovio.structure.adt.Set;

/**
 * 二叉排序树
 *
 * @author AtoVio, Winter Yuan
 * @version 1.0
 */
public class BinarySortTree<T extends Comparable<? super T>>
        extends TriBinaryTree<T> implements Set<T> {

    // 根结点
    public TriNode<T> root;

    // 构造空二叉排序树
    public BinarySortTree() {
        super();
    }

    // 构造二叉排序树，由数组values提供元素
    public BinarySortTree(T[] values) {
        // 构造空二叉树
        this();
        // 插入数组中所有元素
        // 二叉排序树插入元素
        for (T value : values) {
            add(value);
        }
    }

    /**
     * 寻找与value相等的结点
     *
     * @param value 查找值
     * @return 等值的结点
     */
    public TriNode<T> searchNode(T value) {
        TriNode<T> p = root;
        while (p != null && value.compareTo(p.data) != 0) {
            // 若value较小，进入左子树
            if (value.compareTo(p.data) < 0)
                p = p.left;
                // 否则，进入右子树
            else
                p = p.right;
        }
        return p;
    }

    /**
     * 查找与value值相等的结点
     * @param value 查找值
     * @return 相等节点的值
     */
    @Override
    public T search(T value) {
        TriNode<T> p = root;
        while (p != null){
            // 如果相等，找到了
            if (value.compareTo(p.data) == 0)
                return p.data;
            // 如果value小，往左子树找
            if (value.compareTo(p.data) < 0)
                p = p.left;
            else
                p = p.right;
        }
        // 没找到
        return null;
    }

    /**
     * 插入
     * @param value 插入值
     * @return 成功插入返回true,否则返回false
     */
    @Override
    public boolean add(T value) {
        if (value == null)
            return false;
        // 创建根结点
        if (root == null) {
            root = new TriNode<>(value);
        } else {
            TriNode<T> p = root;
            TriNode<T> parent = null;
            // 寻找插入位置
            while (p != null) {
                // 查找到相同元素，返回
                if (value.compareTo(p.data) == 0)
                    return false;
                parent = p;
                if (value.compareTo(p.data) < 0)
                    p = p.left;
                else
                    p = p.right;
            }
            // 找到位置了，插入
            if (value.compareTo(parent.data) < 0)
                parent.left = new TriNode<>(value, parent, null, null);
            else
                parent.right = new TriNode<>(value, parent, null, null);
        }
        return true;
    }

    /**
     * 删除指定值的结点。
     * <p>
     *     分为两种情况：
     *     <li>
     *         待删结点是1度结点，直接更新换代。
     *     </li>
     *     <li>
     *         待删结点是2度结点，寻找待删结点在中序遍历的后继结点insucc，将二者的值互换，再删除该后继结点。
     *         我们可以知道，在中序遍历，一个2度结点的后继结点要么是它的右孩子，要么是它右子树的最小叶子节点。二者都是1度结点。
     *         所以问题转化为删除1度结点。
     *     </li>
     * </p>
     * @param value 待删结点的值
     * @return 待删结点的值
     */
    @Override
    public T remove(T value) {
        // 找到待删结点
        TriNode<T> target = searchNode(value);
        if (target == null) {
            return null;
        }
        // 如果target是2度结点，找到它在中序遍历的后继结点.
        if (target.left != null && target.right != null){
            // insucc 为 target 在中序遍历的后继结点
            TriNode<T> insucc = infixFirst(target.right);
            // 交换target和insucc的值
            T temp = target.data;
            target.data = insucc.data;
            insucc.data = temp;
            // 改为删除insucc结点
            target = insucc;
        }
        // target 是1度的根结点
        if (target == root){
            if (root.left != null)
                root = target.left;
            else
                root = target.right;
            if (root != null)
                root.parent = null;
            return target.data;
        }
        // target 是1度或叶子结点，target是父结点的左孩子
        if (target == target.parent.left){
            // 更新换代
            if (target.left != null){
                target.parent.left = target.left;
                target.left.parent = target.parent;
            } else {
                target.parent.left = target.right;
                if (target.right != null)
                    target.right.parent = target.parent;
            }
        }
        // target 是1度或叶子结点，target是父结点的右孩子
        if (target == target.parent.right){
            // 更新换代
            if (target.left != null){
                target.parent.right = target.left;
                target.left.parent = target.parent;
            } else {
                target.parent.right = target.right;
                if (target.right != null)
                    target.right.parent = target.parent;
            }
        }
        return target.data;
    }

    @Override
    public boolean isEmpty() {
        return root == null;
    }

    @Override
    public void inOrder() {
        System.out.print("(");
        // 寻找第一个访问结点
        TriNode<T> p = this.infixFirst(this.root);
        if (p != null) {
            System.out.print(p.data);
            // 获取下一个要访问的结点
            p = infixNext(p);
        }
        for (; p != null; p = this.infixNext(p))
            System.out.print(", " + p.data);
        System.out.println(")");
    }
}
